//
// Created by ASUS on 2024/10/18/星期五.
//

#include <bits/stdc++.h>
using namespace std;


int minDistance(vector<int>& houses, int k) {
	int n = houses.size();
	sort(houses.begin(), houses.end());
	vector<vector<int>> g(n, vector<int>(n));
	for (int i = n - 2; i >= 0; --i) {
		for (int j = i + 1; j < n; ++j) {
			g[i][j] = g[i + 1][j - 1] + houses[j] - houses[i];
		}
	}
	vector<vector<int>> f(n, vector<int>(k + 1, INT_MAX / 2));
	for (int i = 0; i < n; ++i) {
		f[i][1] = g[0][i];
		for (int j = 2; j <= min(k,i+1); ++j) {
			for(int l=0;l<i;l++){
				f[i][j]=min(f[i][j],f[l][j-1]+g[l+1][i]);
			}
		}
	}
	return f[n - 1][k];
}